package cn.im;

import java.util.HashMap;
import java.util.Map;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        //5. 最长回文子串
        System.out.println(solution.longestPalindrome("aacabdkacaa"));
    }


    /**
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * https://leetcode-cn.com/problems/longest-palindromic-substring/
     * 解答：暴力破解、动态规划、中心扩散
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if (s.length() <=1){
            return  s;
        }

        String target = s.substring(0,1);
        int left=0,win=1;
        char[] chars = s.toCharArray();
        for (int i=0 ; i< chars.length; i++){
            for (int j = i+1 ; j<chars.length; j++){
                if(chars[i] == chars[j] && compare(chars,i,j)){
                    target = target.length()<(j-i+1)?s.substring(i,(j==chars.length-1?chars.length:j+1)):target;
                }
            }
        }

        return target;
    }

    public boolean compare(char[] chars,int i ,int j){
        int left = i;
        int right = j;
        while (left < right){
            if(chars[left] == chars[right]){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }

}
